package com.adamjwh.sort;

/**
 * 快速排序
 * 
 * @author adamjwh
 * 
 * 算法描述：
 * 从数列中挑出一个元素，称为 “基准”（pivot）；
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 *
 */
public class QuickSort {
	
	public static void quickSort(int[] array, int lo, int hi) {
		if(lo >= hi) {
			return;
		}
		
		//进行第一轮排序获取分割点
		int index = partition(array, lo, hi);
		//排序前半部分
		quickSort(array, lo, index-1);
		//排序后半部分
		quickSort(array, index+1, hi);
		
	}
	
	/**
	 * 一次快速排序
	 * @param array
	 * @param lo
	 * @param hi
	 * @return key的下标index，也就是分片的间隔点
	 */
	public static int partition(int[] array, int lo, int hi) {
		int key = array[lo];
		
		while(lo<hi) {
			//从后半部分向前扫描
			while(array[hi]>=key && hi>lo) {
				hi--;
			}
			array[lo] = array[hi];
			
			//从前半部分向后扫描
			while(array[lo]<=key && hi>lo) {
				lo++;
			}
			array[hi] = array[lo];
		}
		array[hi] = key;	//存入基准
		
		return hi;
	}
	
	//测试
	public static void main(String[] args) {
	    int[] arr = {1,9,3,12,7,8,3,4,65,22};

	    quickSort(arr, 0, arr.length-1);

	    for(int i:arr){
	        System.out.print(i+",");
	    }
	}

}
